package com.kevinkk.tree;

/**
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。、
 * 返回二叉搜索树（有可能被更新）的根节点的引用。
 */

/**
 * 删除节点时需要考虑三种情况
 * 1. 该节点无左右孩子，那么直接删除该节点即可，返回空
 * 2. 该节点只有一边有孩子，那么直接删除该节点，返回它剩下的孩子即可
 * 3. 该节点两边都有孩子，那么需要对其进行调整
 * 要么，将其左子树放到右子树的最左下脚，要么，将其右子树放到左子树的最右下角
 */

public class DeleteNodeInABst {
    class Solution {
        public TreeNode deleteNode(TreeNode root, int val) {
            if (root == null) return null;
            if (root.val == val) {
                if (root.left == null && root.right == null) return null;        // 情况1️⃣
                if (root.left != null && root.right == null) return root.left;   // 情况2️⃣
                if (root.left == null && root.right != null) return root.right;  // 情况2️⃣
                // 情况3️⃣： 这里将右子树放到最左下脚
                TreeNode temp = root.left;
                while (temp.right != null)
                    temp = temp.right;
                temp.right = root.right;
                return root.left;   // 注意要返回 root.left，相当于删除 root
            }

            if (root.val > val) root.left = deleteNode(root.left, val);
            if (root.val < val) root.right = deleteNode(root.right, val);
            return root;
        }
    }
}
